# Read the solution [Here](https://quastor.org/cracking-the-coding-interview/trees-and-graph/minimal-tree)

# Minimal Tree

## Cracking the Coding Interview 4.2

<br />

# Question

You are given a **sorted** array with unique integer elements as input.

<br />

Write an algorithm that creates a binary search tree with minimal height from that array.

<br />

<details>
  <summary>Solution</summary>

This question is actually quite a bit easier than it may seem. We can solve it using recursion!

<br />

We first find the middle element of the sorted array. All the numbers before will be less than this element and all the numbers after will be greater than (because the array is sorted).

<br />

Additionally, the number of elements before our middle will be approximately equal to the number of elements after our middle (because we've picked the middle of the list).

<br />

So now, we can create the root node of our BST using the middle element.

<br />

Then, we recursively call our function to create another BST for all the elements on the left (all the elements less than our middle). That BST becomes our left child.

<br />

We recursively call our function again to create a BST for all the elements on the right (all the elements greater than our middle). That BST becomes our right child.

<br />

The base case for our recursive function will be if we get an empty array. Then we can just return `None`.

<br />

After creating both the left and right subtrees, we can return our tree!

<br />

The time complexity is $$O(n)$$.

<br />

This is because our function can be represented by the recurrence

<br />

$$T(n) = 2 \cdot T(\dfrac{n}{2}) + c$$

<br />

Using the Master Method, we know that means our time complexity is $$O(n)$$.

<br />

Learn about the Master Method <a href="https://quastor.org/learn/time-complexity/master-method" target="_blank">here.</a>

<br />

The space complexity is also $$O(n)$$.
    
```python
class TreeNode:
    def __init__(self, val = None):
        self.val = val
        self.left = None
        self.right = None

def createBST(nums):
    if len(nums) == 0:
        return None
    
    middle = len(nums) // 2
    
    root = TreeNode(nums[middle])
    root.left = createBST(nums[:middle])
    root.right = createBST(nums[middle + 1:])
    
    return root
```

<a href="https://repl.it/@quastortech/Solution-4#main.py" target="_blank">Here's a Python 3 REPL with the code.</a>
</details>